package a10_动态规划;

import java.util.Scanner;

/**
 * <p>
 * a11_背包理论基础1
 * </p>
 *
 * @author flyduck
 * @since 2025/2/10
 */
public class a11_背包理论基础1 {
    //dp[i][j]含义：下标[0,i]之间的物品任取放进容量为j的背包里面的最大价值

    //递推公式：
    //不放物品i：最大价值就是dp[i-1][j]
    //放物品i：最大价值就是dp[i-1][j-weight[i]] + value[i]

    //如何初始化
    //dp[i][j]是由上面的和左上面的推导出来的
    //因此我们初始化：dp[0][0] -> dp[0][j]
    //因此我们初始化：dp[0][0] -> dp[i][0]

    //物品   重量    价值
    //物0     1       15
    //物1     3       20
    //物2     4       30
    //   0  1  2  3  4
    //0  0  15 15 15 15
    //1  0
    //2  0

    //遍历顺序
    //for()//物品
    // for()//重量
    public static void main(String[] args) {
        ///////////////////////////////////////
//        Scanner scanner = new Scanner(System.in);
//
//        int number = scanner.nextInt();
//        int totalWeight = scanner.nextInt();
//
//        int[] weightArray = new int[number];
//        int[] valueArray = new int[number];
//
//        for (int i = 0; i < weightArray.length; i++) {
//            weightArray[i] = scanner.nextInt();
//        }
//
//        for (int i = 0; i < valueArray.length; i++) {
//            valueArray[i] = scanner.nextInt();
//        }

        ////////////////////////////////////////


        int number = 6;
        int totalWeight = 1;

        int[] weightArray = new int[]{2,2,3,1,5,2};
        int[] valueArray = new int[]{2,3,1,5,4,3};



        int[][] dp = new int[number][totalWeight+1];
        for (int i = 0; i < number; i++) {
            dp[i][0] = 0;
        }

        for (int j = 0; j <= totalWeight; j++) {
            if(j >= weightArray[0]){
                dp[0][j] = valueArray[0];
            }
        }

        for (int i = 1; i < number; i++) {
            for (int j = 1; j <= totalWeight; j++) {
                if(j >= weightArray[i]){
                    dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-weightArray[i]]+valueArray[i]);
                }else {
                    dp[i][j] = dp[i-1][j];
                }

            }
        }

        System.out.println(dp[number-1][totalWeight]);
    }
}
